Smallest distinct window
Given a string 's'. The task is to find the smallest window length that contains all the characters
of the given string at least one time.For eg. A = “aabcbcdbca”, then the result would be 4 as of the
smallest window will be “dbca”.
Example 1:
Input : "AABBBCBBAC"
Output : 3
Explanation : Sub-string -> "BAC"
Example 2:
Input : "aaab"
Output : 2
Explanation : Sub-string -> "ab"
Code
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
int i,j,n,k,mn=INT_MAX;
cin>>s;
n=s.size();
unordered_map<char,int>m,m1;
for(i=0;i<n;i++)
{
m1[s[i]]++;
}
k=m1.size();
i=0,j=0;
while(j<n)
{
m[s[j]]++;
if(m.size()<k)
j++;
else if(m.size()==k)
{
mn=min(mn,j-i+1);
while(m.size()==k)
{ mn=min(mn,j-i+1);
m[s[i]]--;
if(m[s[i]]==0)
m.erase(s[i]);
i++;
}
j++;
}
}
cout<<mn<<endl;
return 0;
}